package xiaohong.search;

import java.util.Arrays;

import static xiaohong.sort.RadixSortDemo.radixSort;

public class AverageSearchDemo {

    public static void main(String[] args) {
        int[] arr = {12, 11, 15, 50, 7, 65, 3, 99,100,101};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
        int result = fibonacciSearch(arr, 101);
        if (result != -1) {
            System.out.println("目标元素 " + 101 + " 在数组中的索引位置为: " + result);
        } else {
            System.out.println("目标元素 " + 101 + " 未找到");
        }
    }

    public static int[] fibonacci(){
        int[] f = new int[20];
        int i =0;
        f[0] = 1;
        f[1] = 1;
        for(i=2;i<f.length;i++){
            f[i] = f[i-1]+f[i-2];
        }
        System.out.println(Arrays.toString(f));
        return f;
    }

    public static int fibonacciSearch(int[] data,int key){
        int low = 0;
        int high = data.length-1;
        int mid = 0;

        //斐波那契分割数值下标
        int k = 0;

        //序列元素个数
        int i=0;

        // 获取斐波那契数列
        int[] f = fibonacci();

        //获取斐波那契分割数值下标
        while(data.length>f[k]-1){
            k++;
        }
        //创建临时数组
        int[] temp = new int[f[k]-1];
        System.arraycopy(data, 0, temp, 0, data.length);

        //序列补充至f[k]个元素
        //补充的元素值为最后一个元素的值
        for(i=data.length;i<f[k]-1;i++){
            temp[i]=temp[high];
        }

        for(int j:temp){
            System.out.print(j+" ");
        }
        System.out.println();

        while( low <= high )
        {
            // low：起始位置
            // 前半部分有f[k-1]个元素，由于下标从0开始
            // 则-1 获取 黄金分割位置元素的下标
            mid = low + f[k-1] - 1;
            if( temp[mid] > key )
            {
                // 查找前半部分，高位指针移动
                high = mid - 1;
                //将 k 减去 1，表示我们要查找前半部分。
                // 因为前半部分有 f[k-1] 个元素，所以我们更新 k = k - 1;。
                k = k - 1;
            }else if( temp[mid] < key )
            {
                // 查找后半部分，低位指针移动
                low = mid + 1;
                //将 k 减去 2，表示我们要查找后半部分。
                // 因为后半部分有 f[k-2] 个元素，所以我们更新 k = k - 2;。
                k = k - 2;
            }else{
                //如果为真则找到相应的位置
                if( mid <= high )
                {
                    return mid;
                }else{
                    //出现这种情况是查找到补充的元素
                    //而补充的元素与high位置的元素一样
                    return high;
                }
            }
        }
        return -1;
    }






}
